package com.my.study.algorithm.leetcode;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

/**
 * 复杂链表的复制
 * <p>
 *     请实现 copyRandomList 函数，复制一个复杂链表。
 *     在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
 *     
 *     复杂链表复制涉及了链表复制和链表拆分两大基础知识，需要好好掌握。
 * </p>
 * 
 * @author Carlos
 * @version 1.0.0
 * @date 2023/1/9 21:53
 */
public class CopyOfComplex {


    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Map<Node, Node> map = new HashMap<>(2);
        Node cur = head;
        
        // 1.构建字典表
        while (cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        
        // 2.构建新链表的next和random
        cur = head;
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        
        return map.get(head);
    }

    public Node copyRandomList1(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        // 1.复制各节点，并构建拼接链表
        while (cur != null) {
            Node tmp = new Node(cur.val);
            tmp.next = cur.next;
            cur.next = tmp;
            cur = tmp.next;
        }

        // 2. 构建各新节点的 random 指向
        cur = head;
        while (cur != null) {
            if (cur.random != null) {
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }
        
        // 3.拆分链表
        cur = head.next;
        Node pre = head, res = head.next;
        while (cur.next != null) {
            pre.next = pre.next.next;
            cur.next = cur.next.next;
            pre = pre.next;
            cur = cur.next;
        }
        
        // 4.单独处理原链表尾部
        pre.next = null;
        
        return res;
    }
    

    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (o == null || getClass() != o.getClass()) {
                return false;
            }
            Node node = (Node) o;
            return val == node.val &&
                    Objects.equals(next, node.next) &&
                    Objects.equals(random, node.random);
        }

        @Override
        public int hashCode() {
            return Objects.hash(val, next, random);
        }
    }
    
    
    
    /**
     * 简单链表复制
     * 
     * @param head:   
     * @return Node
     * @author Carlos
     * @date 2023/1/10 21:59
     */
    private Node simpleCopyRandomList(Node head) {
        Node cur = head;
        Node newHead = new Node(0);
        Node pre = newHead;
        while (cur != null) {
            Node node = new Node(cur.val);
            pre.next = node;
            cur = cur.next;
            pre = node;
        }

        return newHead.next;
    }
}
